package de.jmda.util.gui.awt.graphics;

import java.awt.Point;
import java.awt.Polygon;

public abstract class Compass
{
	private final static int MAX = Integer.MAX_VALUE;

	public enum Direction
	{
		NORTH,
		//	              NORTH_NORTH_EAST,
		//	              NORTH_NORTH_WEST,
		EAST,
		//	              EAST_NORTH_EAST,
		//	              EAST_SOUTH_EAST,
		SOUTH,
		//	              SOUTH_SOUTH_EAST,
		//	              SOUTH_SOUTH_WEST,
		WEST,
		//	              WEST_SOUTH_WEST,
		//	              WEST_NORTH_WEST
		NONE
	}

	/**
	 * Computes the direction in that <code>target</code> is located in relation
	 * to <code>source</code>. The algorithm constructs polygons starting at
	 * <code>source</code> and then defines areas which span all points that are
	 * located north, east, south and west from <code>source</code>. The direction
	 * in which <code>target</code> is located is found if <code>target</code> is
	 * contained in one of those areas.
	 * <p>
	 * <code>
	 * 0|12345<br>
	 * -+-----<br>
	 * 1|nnnne<br>
	 * 2|wnnee<br>
	 * 3|wwoee<br>
	 * 4|wwsse<br>
	 * 5|wssss<br>
	 * </code>
	 *
	 * @param source
	 * @param target
	 * @return direction (see above)
	 */
	public static Direction getDirection(Point source, Point target)
	{
		if (source.x < 0 ||
		    source.y < 0 ||
		    target.x < 0 ||
		    target.y < 0)
		{
			// source or target are out of polygon bounds
			return Direction.NONE;
		}
		
		if (source.equals(target))
		{
			return Direction.NONE;
		}

		Polygon polygon = new Polygon();

		// start polygon at source
		polygon.addPoint(source.x, source.y);

		// check north
		if (source.x < source.y)
		{
			// polygon spans
			polygon.addPoint(0                      , source.y - source.x);
			polygon.addPoint(0                      , 0                  );
			polygon.addPoint(source.x + source.y - 1, 0                  );
		}
		else if (source.x == source.y)
		{
			// polygon spans
			polygon.addPoint(0                      , 0);
			polygon.addPoint(source.x + source.y - 1, 0);
		}
		else
		{
			// polygon spans
			polygon.addPoint(source.x - source.y    , 0);
			polygon.addPoint(source.x + source.y - 1, 0);
		}

		// finish polygon span at source
		polygon.addPoint(source.x, source.y);

		if (polygon.contains(target))
		{
			return Direction.NORTH;
		}
		
		polygon.reset();

		// start polygon at source
		polygon.addPoint(source.x, source.y);

		// check east
		if (source.x < source.y)
		{
			// polygon spans
			polygon.addPoint(source.x + source.y              , 0  );
			polygon.addPoint(MAX                              , 0  );
			polygon.addPoint(MAX                              , MAX);
			polygon.addPoint(MAX - (source.y - (source.x + 1)), MAX);
		}
		else if (source.x == source.y)
		{
			polygon.addPoint(source.x + source.y, 0      );
			polygon.addPoint(MAX                , 0      );
			polygon.addPoint(MAX                , MAX - 1);
		}
		else
		{
			// polygon spans
			polygon.addPoint(source.x + source.y, 0                   );
			polygon.addPoint(MAX                , 0                   );
			polygon.addPoint(MAX                , MAX - (source.y - 1));
		}

		// finish area at source
		polygon.addPoint(source.x, source.y);

		if (polygon.contains(target))
		{
			return Direction.EAST;
		}
		
		polygon.reset();

		// start polygon at source
		polygon.addPoint(source.x, source.y);

		// check south
		if (source.x < source.y)
		{
			// polygon spans
			//                                          - 1 due to a bug in polygon.contains()
			polygon.addPoint(MAX - (source.y - source.x - 1), MAX                    );
			polygon.addPoint(0                              , MAX                    );
			polygon.addPoint(0                              , source.x + source.y + 1);
		}
		else if (source.x == source.y)
		{
			// polygon spans
			//                        - 1 due to a bug in polygon.contains()
			polygon.addPoint(MAX, MAX - 1                );
			polygon.addPoint(0  , MAX                    );
			polygon.addPoint(0  , source.x + source.y + 1);
		}
		else
		{
			// polygon spans
			polygon.addPoint(MAX, MAX - source.y         );
			polygon.addPoint(MAX, MAX                    );
			polygon.addPoint(0  , MAX                    );
			polygon.addPoint(0  , source.x + source.y + 1);
		}

		// finish area at source
		polygon.addPoint(source.x, source.y);

		if (polygon.contains(target))
		{
			return Direction.SOUTH;
		}
		
		polygon.reset();

		// start polygon at source
		polygon.addPoint(source.x, source.y);

		// check west
		if (source.x < source.y)
		{
			// polygon spans
			//                                      + 1 due to a bug in polygon.contains()
			polygon.addPoint(0, source.y + source.x + 1);
			polygon.addPoint(0, source.y - (source.x + 1));
		}
		else if (source.x == source.y)
		{
			// polygon spans
			//                                      + 1 due to a bug in polygon.contains()
			polygon.addPoint(0, source.y + source.x + 1);
			polygon.addPoint(0, 0 + 1                  );
		}
		else
		{
			// polygon spans
			//                                                            + 1 due to a bug in polygon.contains()
			polygon.addPoint(0                      , source.y + source.x + 1);
			polygon.addPoint(0                      , 0                  );
			polygon.addPoint(source.x + source.y - 1, 0                  );
		}

		// finish area at source
		polygon.addPoint(source.x, source.y);

		if (polygon.contains(target))
		{
			return Direction.WEST;
		}
//		else
//		{
//			// there seems to be a bug in Polygon.contains() method, here is the
//			// workaround
//			if (((source.x - target.x) ==  1) &&
//			    ((source.y - target.y) == -1))
//			{
//				return Direction.WEST;
//			}
//			else if (((source.x - target.x) == -1) &&
//			         ((source.y - target.y) == -1))
//			{
//				return Direction.SOUTH;
//			}
//		}

		throw new RuntimeException(
				"failure calculating direction for\n" +
				"source: x = " + source.x + ", y = " + source.y + "\n" +
				"target: x = " + target.x + ", y = " + target.y);
	}
}